1. Field of the Invention
The present invention relates to a branch instruction execution control apparatus in an information processing device for executing sequentially input instructions, and more specifically to a branch instruction execution control apparatus for controlling the execution of a branch instruction in an information processing device for sequentially referring to and updating the resources accessible from a program, that is, the contents of a storage area of memory, the register, etc. in the program instruction execution order.
2. Description of the Related Art
In an information processing device, various techniques have been used to quickly process instructions. One of those is a pipeline processing. There is a system called ‘super-pipeline’ for attaining high performance by realizing a high-speed machine cycle with a larger number of stages in the pipeline processing, a super-scalar system having a plurality of pipelines, etc.
The second technology is a system realized to control the execution of an instruction by providing a stack waiting for a process referred to as reservation station instead of controlling the execution of an instruction through a pipeline. In the system using the reservation station, unlike the pipeline system, the number of entries in a stack can be selected independent of the number of process steps in machine cycle units. Thus, a higher-level concurrent process can be performed by increasing the number of entries.
The third technology is an out-of-order system for aiming at higher performance. An out-of-order system refers to a system of executing instructions in an order different from the instruction order specified by a program, for example, in order from an instruction for which input data has been ready. That is, in the out-of-order system, an entry which can be processed in a stack is selected, and a process corresponding to the entry is performed in an order different from the instruction order specified by a program, thereby realizing a high-level concurrent process.
In the out-of-order system, instructions are executed in an optional order, but it is necessary to execute the instructions such that the resources accessible by a program, that is, the contents of a storage area of memory, a register, etc., can be referenced and updated in the execution order of the program.
In the information processing device for quickly processing instructions, for example, the system starts executing a sequence of instructions without waiting for the completion of the execution of a precedent instruction, and the concurrent process can improve the entire performance.
However, when the execution result of a precedent instruction has an influence on the subsequent instructions, it is necessary to sequentially process the instructions, thereby causing the performance of the information processing device to be deteriorated. A typical example is a branch instruction. When a branch instruction is used, it is not certain until the completion of the execution whether or not the branch is selected, and what the instruction address is.
To quickly process a sequence of instructions containing a branch instruction, a mechanism of executing a branch instruction in parallel with instructions other than a branch instruction is first required. Without the mechanism, instructions are sequentially processed each time a branch instruction is executed, and the hardware resources prepared for parallel execution cannot be effectively utilized, thereby deteriorating the performance.
In addition, for a high-speed process, an instruction subsequent to a branch instruction should be speculatively executed. If a branch instruction is started without such speculative execution of instructions, the execution of the instructions subsequent in execution order to the branch instruction cannot be started until the branch instruction has been completely executed, thereby interfering with the effective use of hardware resources for concurrent execution.
Thus, instructions to be speculatively executed after a branch instruction can be a sequence of instructions subsequent to the branch instruction assuming that the branch instruction is selected. Additionally, by providing a branch prediction mechanism, sequence of instructions at a branched-to address for use when a branch instruction is selected can also be instructions to be speculatively executed.
However, when instructions subsequent to a branch instruction are speculatively executed to quickly process a sequence of instructions containing the branch instruction, it is necessary to provide a mechanism for validating the speculative execution depending on the execution result of the precedent branch instruction, and a mechanism for deleting the execution of the instruction and re-executing a correct sequence of instructions if the speculative execution of an instruction is not valid. Furthermore, it is hard to improve the performance unless the information of the branch prediction mechanism can be appropriately updated depending on an execution result.
If there is another branch instruction in a sequence of instructions to be speculatively executed, and if the execution of the subsequent instructions is delayed until the branch instruction has been completely executed, then the performance of a sequence of instructions containing a larger number of branch instructions is deteriorated. In addition, if a sequence of instructions subsequent to the branch instruction in another sequence of instructions to be speculatively executed is also to be speculatively executed, then a mechanism for deleting the speculative execution result of an instruction and a mechanism for re-executing a correct sequence of instructions should be the more complicatedly designed.